package com.itheima.d4_algorithm;

import java.util.Arrays;

/**
 * 目标：掌握二分查找算法。
 */
public class Test3 {
    public static void main(String[] args) {
        // 1、准备好一个数组。
        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
        //           0   1  2

        System.out.println("binarySearch2(arr, 79) = " + binarySearch2(arr, 79));
        System.out.println("binarySearch2(arr,100) = " + binarySearch2(arr, 100));
        //数组工具类Arrays中，也提供了二分查找的方法
        System.out.println("Arrays.binarySearch(arr,79) = " + Arrays.binarySearch(arr, 79));



    }

    public static int binarySearch(int[] arr, int data) {
        // 1、定义两个变量，一个站在左边位置，一个站在右边位置
        int left = 0;
        int right = arr.length - 1;

        // 2、定义一个循环控制折半。
        while (left <= right) {
            // 3、每次折半，都算出中间位置处的索引
            int middle = (left + right) / 2;
            // 4、判断当前要找的元素值，与中间位置处的元素值的大小情况。
            if (data < arr[middle]) {
                // 往左边找，截止位置（右边位置） = 中间位置 - 1
                right = middle - 1;
            } else if (data > arr[middle]) {
                // 往右边找，起始位置（左边位置） = 中间位置 + 1
                left = middle + 1;
            } else {
                // 中间位置处的元素值，正好等于我们要找的元素值
                return middle;
            }
        }
        return -1; // -1特殊结果，就代表没有找到数据！数组中不存在该数据！
    }

    //写一个方法实现二分查找，传入一个数组，及要查找的元素。返回该元素在数组中的索引位置。如果不存在返回-1
    public static int binarySearch2(int[] arr, int data) {
        int left = 0;//开始位置
        int right = arr.length - 1;//结束位置
        //循环来模拟查找操作
        while (left<=right) {
            //计算中间位置，比较中间位置元素和传入的data大小
            int mid = (left + right) / 2;
            if (arr[mid] < data) {
                //中间以左的数据可以排除，更新左边界为mid+1
                left = mid + 1;
            } else if (arr[mid] > data) {
                //中间以右的数据可以排除，更新右边界为mid-1
                right = mid - 1;
            } else {
                //中间位置的数据正好是要找的数据对应的索引
                return mid;
            }
        }


        //如果不存在返回-1
        return -1;
    }


}
